package com.smh;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author shiminghui
 * @date 2025/3/12 16:03
 * @description: TODO
 */
public class _039_sort {

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 冒泡排序
     */
    private void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int flag = 0;
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = 1;
                }
            }
            if (flag == 0) {
                break;
            }
        }
    }

    private void bubbleSort2(int[] arr) {
        int right = arr.length - 1;
        int tempRight;
        while (right > 0) {
            tempRight = -1;
            for (int i = 0; i < right; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    tempRight = i;
                }
            }
            right = tempRight;
        }
    }

    @Test
    public void test1() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2};
        bubbleSort2(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 选择排序
     *
     * @param arr
     */
    private void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                    // 如果交换代码放在这里的话,每次可能有多次交换
                }
            }
            if (min != i) { // 这样每次只有交换一次
                swap(arr, i, min);
            }
        }
    }

    @Test
    public void test2() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2};
        selectSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 插入排序
     */
    private void insertSort(int[] arr) {
        int low = 1;
        while (low < arr.length) {
            int left = low;
            int temp = arr[low];
            while (left > 0 && arr[low] < arr[left - 1]) {
                left--;
            }
            System.arraycopy(arr, left, arr, left + 1, low - left);
            arr[left] = temp;
            low++;
        }
    }

    @Test
    public void test4() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2};
        insertSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 堆排序
     */
    private void heapSort(int[] arr) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            heap.offer(arr[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.poll();
        }
    }

    private void heapSort2(int[] arr) {
        heapify(arr, arr.length);
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            down(arr, 0, i);
        }
    }

    private void heapify(int[] arr, int length) {
        for (int i = length / 2 - 1; i >= 0; i--) {
            down(arr, i, length);
        }
    }

    private void down(int[] arr, int parent, int length) {
        while (true) {
            int left = parent * 2 + 1;
            int right = parent * 2 + 2;
            int max = parent;
            if (left < length && arr[left] > arr[max]) {
                max = left;
            }
            if (right < length && arr[right] > arr[max]) {
                max = right;
            }
            if (max == parent) {
                break;
            }
            swap(arr, max, parent);
            parent = max;
        }
    }


    @Test
    public void test3() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2};
        heapSort2(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 希尔排序
     * 希尔排序是插入排序的升级版，插入排序每次都是相邻的元素进行比较，
     * 而希尔排序每次都是跨度大的元素进行比较，跨度越大，效率越低，但是跨度越大，排序越快。
     * 希尔排序比堆排序的效率要高，但是希尔排序的效率和跨度有关，跨度越大，效率越低。
     */
    private void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 0) {
            for (int i = 0; i < gap; i++) {
                int low = i + gap;
                while (low < arr.length) {
                    int left = low;
                    int temp = arr[low];
                    while (left > 0 && arr[low] < arr[left - 1]) {
                        left -= gap;
                    }
                    for (int j = low; j > left; j -= gap) {
                        arr[j] = arr[j - gap];
                    }
                    arr[left] = temp;
                    low += gap;
                }
                gap = gap >> 1;
            }
        }
    }

    @Test
    public void test5() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2};
        shellSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 归并排序
     */
    private void mergeSort(int[] arr) {
        split(arr, 0, arr.length - 1, new int[arr.length]);
    }

    private void split(int[] arr, int left, int right, int[] temp) {
        // 治
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        // 分割
        split(arr, left, mid, temp);
        split(arr, mid + 1, right, temp);
        // 合并
        merge(arr, left, mid, mid + 1, right, temp);
        System.arraycopy(temp, left, arr, left, right - left + 1);
    }

    private void merge(int[] arr, int left, int leftEnd, int right, int rightEnd, int[] temp) {
        int index = left;
        while (left <= leftEnd && right <= rightEnd) {
            if (arr[left] < arr[right]) {
                temp[index] = arr[left];
                left++;
            } else {
                temp[index] = arr[right];
                right++;
            }
            index++;
        }
        if (left <= leftEnd) {
            while (left <= leftEnd) {
                temp[index] = arr[left];
                left++;
                index++;
            }
        } else {
            while (right <= rightEnd) {
                temp[index] = arr[right];
                right++;
                index++;
            }
        }
    }

    /**
     * 不使用递归,跟递归的效率差不多,所以使用递归更容易理解
     *
     * @param arr
     */
    private void mergeSort2(int[] arr) {
        int length = arr.length;
        int[] temp = new int[length];
        int space = 2; // 跨度
        while (space <= length) {
            for (int i = 0; i < arr.length; i += space) {
                int left = i;
                int leftEnd = (i + space / 2 - 1) >= length ? length - 1 : i + space / 2 - 1;
                int right = (leftEnd + 1) >= length ? length - 1 : leftEnd + 1;
                int rightEnd = (i + space - 1) >= length ? length - 1 : i + space - 1;
                if (left == rightEnd) {
                    temp[left] = arr[left];
                    continue;
                }
                merge(arr, left, leftEnd, right, rightEnd, temp);
            }
            System.arraycopy(temp, 0, arr, 0, length);
            space = space << 1;
        }
    }

    @Test
    public void test6() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2, 6};
        mergeSort2(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 插入排序+归并排序,效率高
     */
    private void insertAndMergeSort(int[] arr) {
        split2(arr, 0, arr.length - 1, new int[arr.length]);
    }

    private void split2(int[] arr, int left, int right, int[] temp) {
        // 没必要划分到最小的情况,在数据量很小时,可以使用插入排序提高效率
//        if (left >= right) {
//            return;
//        }
        if (right - left <= 32) {
            insertSort(arr, left, right);
            return;
        }

        int mid = (left + right) >> 1;
        split2(arr, left, mid, temp);
        split2(arr, mid + 1, right, temp);
        merge(arr, left, mid, mid + 1, right, temp);
        System.arraycopy(temp, left, arr, left, right - left + 1);
    }

    private void insertSort(int[] arr, int left, int right) {
        for (int low = left + 1; low <= right; low++) {
            int temp = arr[low];
            int tempLow = low - 1;
            while (tempLow >= left && arr[tempLow] > temp) {
                tempLow--;
            }
            System.arraycopy(arr, tempLow + 1, arr, tempLow + 2, low - tempLow - 1);
            arr[tempLow + 1] = temp;
        }
    }

    @Test
    public void test7() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2, 6};
        insertAndMergeSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 快排
     */
    private void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition3(arr, left, right);
        quick(arr, left, p - 1);
        quick(arr, p + 1, right);
    }

    // 快排的分区算法(单边循环,右侧为基准点)
    private int partition(int[] arr, int left, int right) {
        // 将最右边的元素作为基准
        int i = left;
        int j = left;
        while (j < right) {
            // j 遍历走,然后j走到了比基准点大的位置时,i停了下来,然后,j再往后走,再找到小的数,交换两数,然后j继续往后走
            if (arr[j] < arr[right]) {
                if (i != j) {
                    swap(arr, i, j); // 即j找到了小的数,i找到了大的数,那么就将小的数放在左边,大的数放在右边
                }
                i++;
            }
            j++;
        }
        swap(arr, i, right);
        return i;
    }

    /**
     * 快排的分区算法(双边循环,左边为基准点)
     */
    private int partition2(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        int p = arr[i];
        while (i < j) {
            // 我们也可以让一边先动完,顺序不要变
            while (arr[j] > p && i < j) {
                j--;
            }
            while (arr[i] <= p && i < j) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        if (i != left) {
            swap(arr, i, left);
        }
        return i;
    }

    /**
     * 随机基准点,然后套用 partition2,避免倒序的情况造成的分区不合理
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partition3(int[] arr, int left, int right) {
        Random random = new Random();
        int randomIndex = random.nextInt(right - left + 1);
        swap(arr, left + randomIndex, left);
        int i = left;
        int j = right;
        int p = arr[i];
        while (i < j) {
            while (arr[j] > p && i < j) {
                j--;
            }
            while (arr[i] <= p && i < j) {  // 这里为啥是<=,因为是从基准点出发的
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        if (i != left) {
            swap(arr, i, left);
        }
        return i;
    }

    /**
     * 随机基准点,然后处理重复的情况,使分区合理
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partition4(int[] arr, int left, int right) {
        Random random = new Random();
        int randomIndex = random.nextInt(right - left + 1);
        swap(arr, left + randomIndex, left);
        int i = left + 1;
        int j = right;
        int p = arr[left];
        while (i <= j) {
            while (i <= j && arr[j] > p) {
                j--;
            }
            while (i <= j && arr[i] < p) {
                i++;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if (j != left) {
            swap(arr, j, left);
        }
        return j;
    }

    @Test
    public void test8() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2, 6};
//        partition2(ints, 0, ints.length - 1);
        quickSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 计数排序
     */
    private void countSort(int[] arr) {
        // 找出最大值,使用stream流
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        for (int k : arr) {
            count[k]++;
        }
        for (int i = 0, j = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[j++] = i;
                count[i]--;
            }
        }

    }

    private void countSort2(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int[] count = new int[max - min + 1];
        for (int k : arr) {
            count[k - min]++;
        }
        for (int i = 0, j = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[j++] = i + min;
                count[i]--;
            }
        }
    }

    @Test
    public void test9() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2, 6, -1};
        countSort2(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 桶排序
     */
    private void bucketSort(int[] arr, int n) {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int num = (max - min) / n + 1; // 桶的数量
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
        // 创建桶
        for (int i = 0; i < num; i++) {
            buckets.add(new ArrayList<>());
        }
        // 放入数据
        for (int i = 0; i < arr.length; i++) {
            int index = (arr[i] - min) / n;
            buckets.get(index).add(arr[i]);
        }
        // 桶排序
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }
        // 输出
        int index = 0;
        for (int i = 0; i < buckets.size(); i++) {
            ArrayList<Integer> bucket = buckets.get(i);
            for (int j = 0; j < bucket.size(); j++) {
                arr[index++] = bucket.get(j);
            }
        }
    }

    @Test
    public void test10() {
        int[] ints = {3, 2, 1, 4, 5, 3, 5, 2, 6, -1};
        bucketSort(ints, 3);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 基数排序
     *
     * @param arr    待排序数组
     * @param length 数组内元素的长度
     */
    private void radixSort(String[] arr, int length) {
        ArrayList<ArrayList<String>> buckets = new ArrayList<>(128);
        for (int i = 0; i < 128; i++) {
            buckets.add(new ArrayList<String>());
        }
        // 找出最大数的位数
        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j < arr.length; j++) {
                buckets.get(arr[j].charAt(i)).add(arr[j]);
            }
            // 再将桶中的数据放回原数组
            int index = 0;
            for (int j = 0; j < buckets.size(); j++) {
                ArrayList<String> bucket = buckets.get(j);
                for (int k = 0; k < bucket.size(); k++) {
                    arr[index++] = bucket.get(k);
                }
                bucket.clear();// 清空桶
            }
        }
    }

    @Test
    public void test11() {
        String[] arr = {"abc", "abd", "abe", "abf", "abg", "abh", "abi", "abj", "abk", "abl", "abm", "abn", "abo", "abp", "abq", "abr", "abs", "abt", "abu", "abv", "abw", "abx", "aby", "abz"};
        radixSort(arr, 3);
        System.out.println(Arrays.toString(arr));
    }

}
